Các mẫu hóa thạch của nhóm này gây nhiều tranh cãi. Giải phẫu độc đáo duy nhất của họ Cu cu (Cuculidae) theo nghĩa cũ thường cho phép dễ dàng nhận dạng thậm chí chỉ từ những mảnh xương cô lập. Các chi chim dạng cu cu tiền sử được biết đến từ Hậu Eocen, vào khoảng 35-40 Ma. Các hóa thạch của turaco chỉ được biết đến muộn hơn. Mẫu hóa thạch được cho là của chim dạng cu cu thuộc Tiền Eocen từ Walton-on-the Naze (Anh) bị nghi ngờ là giả mạo.

Một loạt các hóa thạch khác thời kỳ Paleogen đã từng có thời được gán cho bộ Cuculiformes, nhưng chúng thường không được gộp vào bộ này trong các xử lý gần đây: Họ Gracilitarsidae tồn tại từ Hậu Paleocen tới Trung Eocen ban đầu được coi là chim dạng cu cu nhưng hiện nay nói chung không được chấp nhận như vậy. Dường như chúng vẫn còn là điều bí ẩn, do đặc trưng giải phẫu chỉ xuất hiện ở hậu duệ cuối cùng (apomorph) của chúng, và có thể là gần gũi với họ Sylphornithidae có sự khó hiểu tương đương, được biết đến từ Trung Eocen tới Tiền Oligocen. Từ Tiền Eocen, các chi Parvicuculus và Procuculus có thể là các loài chim thuộc nhánh Cypselomorphae trong dòng dõi cho đến nay vẫn chưa được công nhận. Chi Foro có thể là đồng minh gần của gà móng; nó được coi như là "liên kết bị bỏ sót" giữa loài chim kì dị này với các loài chim bộ Cuculiformes thực thụ như nói trên đây, do thực tế không thể tạo liên kết gần hơn giữa gà móng với bất kỳ loài chim còn sinh tồn nào. Tuy nhiên, phân tích phát sinh chủng loài của Field & Hsiang (2018) chỉ ra rằng Foro có quan hệ họ hàng gần với Musophagidae.[7]